package problems.daily;

/**
 * 1031. 两个非重叠子数组的最大和
 * <p>https://leetcode.cn/problems/maximum-sum-of-two-non-overlapping-subarrays/</p>
 *
 * @author dubulingbo, 2023/04/26, 026 9:27.
 */
public class DT1031 {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int n = nums.length;

        // 1. 从右往左记录第二个数组能取到的最大值
        int[] rmax = new int[n];
        int[] lmax = new int[n];
        int sum = 0;
        int maxSum = 0;
        for (int i = n - 1; i >= 0; --i) {
            sum += nums[i];
            if (i <= n - secondLen) {
                maxSum = Math.max(maxSum, sum);
                rmax[i] = maxSum;
                sum -= nums[i + secondLen - 1];
            }
        }

        // 从右往左记录第二个数组能取到的最大和
        sum = 0;
        maxSum = 0;
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            if (i >= secondLen - 1) {
                maxSum = Math.max(maxSum, sum);
                lmax[i] = maxSum;
                sum -= nums[i - secondLen + 1];
            }
        }

        // 2. 从左往右枚举第一个数组的各个取值，同时记录左边第二个数组可能的最大值
        int firstArrSum = 0;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            firstArrSum += nums[i];
            // 已经能取到第一个数组的长度
            if (i >= firstLen - 1) {
                int secondArrSum = 0;
                // 右边能取到第二个数组的长度
                if (i + 1 < n) {
                    secondArrSum = rmax[i + 1];
                }
                // 左边能取到第二个数组的长度
                if (i - firstLen >= 0) {
                    secondArrSum = Math.max(lmax[i - firstLen], secondArrSum);
                }

                // 更新答案
                ans = Math.max(ans, firstArrSum + secondArrSum);

                firstArrSum -= nums[i - firstLen + 1];
            }
        }

        return ans;
    }


    public static void main(String[] args) {
        DT1031 test = new DT1031();
        System.out.println(test.maxSumTwoNoOverlap(new int[]{
                0, 6, 5, 2, 2, 5, 1, 9, 4}, 1, 2));
    }
}
